<?php
/**
 * 归并排序
 */
class MergeSort
{
    static public function sort($list)
    {
        $count=count($list);
        if($count<=1){
            return $list;
        }
        $middle=floor($count/2);
        $list_1=array_slice($list,0,$middle);
        $list_2=array_slice($list,$middle);
        $list_1=self::sort($list_1);
        $list_2=self::sort($list_2);
        return self::merge($list_1,$list_2);
    }
    static protected function merge($list_1,$list_2)
    {
        $index_1=$index_2=0;
        $list=[];
        while($index_1<count($list_1)){
            if($index_2>=count($list_2)){
                return self::append($list,$list_1,$index_1);
            }
            if($list_1[$index_1] < $list_2[$index_2]){
                $list[]=$list_1[$index_1];
                $index_1++;
            }
            else{
                $list[]=$list_2[$index_2];
                $index_2++;
            }
        }
        return self::append($list,$list_2,$index_2);
    }
    static protected function append($list,$sub_list,$offset)
    {
        for($i=$offset;$i<count($sub_list);$i++){
            $list[]=$sub_list[$i];
        }
        return $list;
    }
}
